package num50;

import num49.Solution;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/5/8 22:23
 * @Desc :
 */
public class Solution3 {
  private HashMap<Long, Double> map = new HashMap<>();

  public double myPow(double x, int n) {
    return recursion(x, n);
  }

  public double recursion(double x, long n) {
    if (n < 0) return recursion(1 / x, -n);
    if (n == 0) return 1;
    if (n == 1) return x;
    Double res = map.get(n);
    if (res != null) return res;
    res = recursion(x, n / 2) * recursion(x, n / 2) * recursion(x, n % 2);
    map.put(n, res);
    return res;
  }

  public static void main(String[] args) {
    double res = new Solution3().myPow(2, -2);
    System.out.println(res);
  }
}
